#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int cmpFunc(const void *a, const void *b) {
    const int *intervalA = *(const int **) a;
    const int *intervalB = *(const int **) b;
    return intervalA[0] - intervalB[0];
}

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes) {
    if (intervalsSize == 0) {
        *returnSize = 0;
        return NULL;
    }

    qsort(intervals, intervalsSize, sizeof(int *), cmpFunc);

    int **outputs = (int **) malloc(sizeof(int *) * intervalsSize);
    int outputsSize = 0;
    outputs[outputsSize++] = intervals[0];
    for (int i = 1; i < intervalsSize; i++) {
        int *lastInterval = outputs[outputsSize - 1];
        int currLeft = intervals[i][0];
        int currRight = intervals[i][1];
        if (lastInterval[1] < currLeft) {
            outputs[outputsSize++] = intervals[i];
        } else {
            lastInterval[1] = lastInterval[1] > currRight ? lastInterval[1] : currRight;
        }
    }

    *returnSize = outputsSize;
    *returnColumnSizes = intervalsColSize;
    return outputs;
}